Routing of shipments between businesses and other locations is a significant problem in commercial environments. The problem of optimally routing shipments can be constructed as the well-known Vehicle Routing Problem (VRP), which is an important optimization problem in operations research. VRPs are an extension of the well-known Travelling Salesman Problem (TSP). In general, VRPs are described as the problem of delivering multiple shipments to multiple locations using multiple vehicles. In solving VRPs, the goals is to define a set of routes subject to capacity, time, or other suitable constraints such that each shipment is delivered in exactly one of the routes while the global cost of these routes is minimized. VRPs belong to a class of difficult problems, referred to as NP-hard problems, for which no efficient solution algorithms are known.
Certain exact algorithms and heuristic procedures have been proposed for solving VRPs. Due to computer processing power and other limitations, the exact algorithms can only be used to solve relatively small VRPs. Exact algorithms also often lack flexibility. Local search heuristics have been effective for solving certain large-scale real-world problems. The general framework for a local search includes two phases: (1) route construction and (2) route improvement. In route construction, initial routes are constructed using various heuristics, such as insertion heuristics. In the improvement phase, local search operations are applied to initial routes to obtain better routes. The most commonly used operations are moving a sequence of stops from one route to another and swapping two sequences of stops between two routes. These operations belong to a class of operations referred to as k-opt.
Although the previous models for solving VRPs have been useful for certain applications, many important practical issues have not been addressed. As a result, it remains important to extend VRP formulation according to real world transportation needs and to develop corresponding solution strategies.